# -*- coding: utf-8 -*-
'''
@Time    : 2022/8/16 22:28
@Author  : HandsomeWu
@File    : buildTree_fromMidLast.py
@Describe:
        从中序与后序遍历序列构造二叉树 -- 并且给出前序遍历的结果

* input:
* output

'''
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# step 1: 根据中序 后序 恢复二叉树
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        # 恢复二叉树
        # 1. 根据后序遍历最后的元素确定根节点 -- 对应中序遍历得到中左 中右子树
        # 2. 根据左右子树的大小 将后序遍历切分为 后左和后右子树
        # 3. 对应分别再递归处理
        # 问题: 树什么时候恢复

        def helper(in_left, in_right):
            # 终止条件 -- 子树为空
            if in_right < in_left:
                return None

            # step1:根据后序找到中点
            val = postorder.pop()
            root = TreeNode(val)

            M_point = idx_map[val]  # 担心会有子树节点相同的 -- 构造成字典就不会了
            # step2: 根据中点切分中序为中左 中右

            root.right = helper(M_point + 1, in_right)
            root.left = helper(in_left, M_point - 1)

            return root

        # 建立 中序哈希表
        idx_map = {val: idx for idx, val in enumerate(inorder)}
        return helper(0, len(inorder) - 1)




# step 2: 二叉树的前序遍历


